package com.peng.leetcode.tree;

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.List;

/**
 * IsValidBST1
 * 98. 验证二叉搜索树
 * https://leetcode.cn/problems/validate-binary-search-tree/
 * <p>
 * Created on 2022/11/27
 *
 * @author lupeng
 */
public class IsValidBST1 {

    // public static void main(String[] args) {
    //     Integer[] arr = new Integer[] {5,4,6,null,null,3,7};
    //     TreeNode treeNode = TreeMain.array2tree(arr);
    //     System.out.println(new IsValidBST1().isValidBST(treeNode));
    // }

    public static void main(String[] args) {
        LocalDateTime localDateTime = LocalDateTime.now().plusSeconds(-1000);
        System.out.println(localDateTime.format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));


    }

    private List<Integer> arr;
    private boolean ans;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        arr = new ArrayList<>();
        ans = true;
        dfs(root);
        return ans;
    }

    void dfs(TreeNode n) {
        if (n == null) {
            return;
        }
        dfs(n.left);
        if (!arr.isEmpty() && arr.get(arr.size() - 1) >= n.val) {
            ans = false;
            return;
        }
        arr.add(n.val);
        dfs(n.right);
    }
}
